/** 
  *https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/submissions/565456030/
 * 1802. 有界数组中指定下标处的最大值
 * medium,  2024.9.14
 * 二分搜索
*/

class Solution {  
public:  
    int maxValue(int n, int index, int maxSum) {  // 定义二分查找的左右边界  
        long long l=1, r=maxSum+1, mid;  
        auto checks=[&](long long x) {  
            long long sum = -x; //初始化
            if (x>index+1) {
                sum+=(2*x-index)*(index+1)/2;
            }  
            else  { 
                sum+=(x+1)*x/2+index+1-x;  
            //计算右侧的和  
            }
            if (x>n-index) { 
                sum+=(2*x-n+index+1)*(n-index)/2;  
            }
            else  {
                sum+=(x+1)*x/2+n-index-x;  
            }
            // 如果和不超过maxSum，则返回true  
            return sum<=maxSum;  
        };  
       
        while(l<r)    // 执行二分查找  
        {   mid=(l+r)>>1; // 取中点  
            if (checks(mid))  
                l=mid+1; // 如果mid满足条件，则尝试更大的范围  
            else  
                r=mid; // 否则，缩小范围到左半部分  
        }  
        // 当二分查找结束时，l指向了第一个不满足条件的mid+1，因此返回l-1即为mid
        return l-1;  
    }  
};